import java.util.Arrays;

public class _132 {
    static class Solution1{
        public int minCut(String s) {
            //是回文为1
            int[][] dp  = new int[s.length()][s.length()];
            char[] chs = s.toCharArray();
            for(int[] arr : dp){
                Arrays.fill(arr,Integer.MAX_VALUE);
            }
            for(int i = 0;i < s.length();i++){
                for(int j = 0;j <= i;j++){
                    if(chs[i] == chs[j] &&( i-j < 2 || dp[j+1][i-1] == 1)){
                        dp[j][i] = 1;
                    }
                }
            }
            //计算minCut
            for(int i = 0;i < dp.length;i++){
                for(int j = 0;j <i;j++){
                    dp[0][i] = Math.min(dp[0][i],dp[0][j] == Integer.MAX_VALUE || dp[j+1][i] == Integer.MAX_VALUE ? Integer.MAX_VALUE : dp[j+1][i]+dp[0][j]);
                }
            }
            return dp[0][dp[0].length-1]-1;

        }
    }
    static class Solution2{
        public int minCut(String s) {
            //discuss的思路
            //核心按照中心开花的方式找回文
            int[] cut = new int[s.length()];
            char[] chs = s.toCharArray();
            for(int i = 0;i < cut.length;i++){
                cut[i] = i;
            }
            for(int i = 0;i < cut.length;i++){
                int[][] cds = {{i,i},{i-1,i}};
                for(int[] c: cds){
                    for(int l=c[0],r=c[1];l >=0 && r < cut.length && chs[l] == chs[r];l--,r++){
                        cut[r] = Math.min(cut[r],l==0 ? 0 : cut[l-1]+1);
                    }
                }
            }
            return cut[cut.length-1];
        }
    }
}
